package main.Q1001_1100;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Q1011_1020 {
    public static void main(String[] args) {
        System.out.println("Question1011：在 D 天内送达包裹的能力");
        int[] weights = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println(new Question1011().shipWithinDays(weights, 5));
        System.out.println("Question1012：");
        System.out.println("Question1013：");
        System.out.println("Question1014：最佳观光组合");
        System.out.println("Question1015：");
        System.out.println("Question1016：");
        System.out.println("Question1017：");
        System.out.println("Question1018：");
        System.out.println("Question1019：链表中的下一个更大节点");
        System.out.println("Question1020：飞地的数量");
    }
}

class Question1011 {
    public boolean process(int[] weights, int days, int max) {
        int temp = 0;
        for (int weight : weights) {
            if (weight > max) {
                return false;
            }
            if (temp + weight > max) {
                temp = 0;
                days--;
            }
            temp += weight;
        }
        return days > 0;
    }

    public int shipWithinDays(int[] weights, int days) {
        int sum = 0;
        for (int weight : weights) {
            sum += weight;
        }
        int left = sum / days, right = sum;
        while (left < right) {
            int mid = (right + left) / 2;
            if (process(weights, days, mid)) {//能运
                right = mid;
            } else {//不能运
                left = mid + 1;
            }
        }
        return left;
    }
}

class Question1014 {
    public int maxScoreSightseeingPair(int[] values) {
        int length = values.length, maxScore = 0, max = values[0] + 0;
        for (int j = 1; j < length; j++) {
            maxScore = Math.max(maxScore, max + values[j] - j);
            max = Math.max(max, values[j] + j);//观光起点最大值
        }
        return maxScore;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Question1019 {
    public int[] nextLargerNodes(ListNode head) {
        List<Integer> nums = new ArrayList<>();
        for (; head != null; head = head.next) {
            nums.add(head.val);
        }
        Deque<Integer> deque = new LinkedList<>();
        int n = nums.size();
        int[] result = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (!deque.isEmpty() && deque.peek() <= nums.get(i)) {
                deque.pop();
            }
            if (!deque.isEmpty()) {
                result[i] = deque.peek();
            }
            deque.push(nums.get(i));
        }
        return result;
    }
}

class Question1020 {
    public int process(int[][] grid, int r, int c) {
        int row = grid.length, col = grid[0].length, count = 1;
        grid[r][c] = 0;
        if (r - 1 >= 0 && grid[r - 1][c] == 1) count += process(grid, r - 1, c);//上
        if (r + 1 < row && grid[r + 1][c] == 1) count += process(grid, r + 1, c);//下
        if (c - 1 >= 0 && grid[r][c - 1] == 1) count += process(grid, r, c - 1);//左
        if (c + 1 < col && grid[r][c + 1] == 1) count += process(grid, r, c + 1);//右
        return count;
    }

    public int numEnclaves(int[][] grid) {
        int landCount = 0, unEnclaveCount = 0, row = grid.length, col = grid[0].length;
        int[][] unGrid = grid.clone();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == 1) {
                    landCount++;
                }
            }
        }
        for (int i = 0; i < col; i++) {
            if (grid[0][i] == 1) {//上侧非飞地
                unEnclaveCount += process(grid, 0, i);
            }
            if (grid[row - 1][i] == 1) {//下侧非飞地
                unEnclaveCount += process(grid, row - 1, i);
            }
        }
        for (int i = 0; i < row; i++) {
            if (grid[i][0] == 1) {//左侧非飞地
                unEnclaveCount += process(grid, i, 0);
            }
            if (grid[i][col - 1] == 1) {//右侧非飞地
                unEnclaveCount += process(grid, i, col - 1);
            }
        }
        return landCount - unEnclaveCount;
    }
}